package 设计题;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/14 15:16
 */
public class leetcode2502内存分配器 {

    public static void main(String[] args) {
        Allocator allocator = new Allocator();
        int is= allocator.hashCode();
        Allocator b = new Allocator();
        System.out.println(b.hashCode());
        System.out.println(new Allocator().hashCode());
        allocator.a = 10;
        Allocator  c = allocator;
        System.out.println(c.hashCode());
        System.out.println(Integer.lowestOneBit(12));
        System.out.println(is);
//        String
        int arr [] = new int[10];

//        for(int  i = 0;i < 10000;i++){
//            arr[new Allocator().hashCode() % 10]++;
//        }
//        System.out.println(Arrays.toString(arr));


    }


}

class Allocator {

    int a;

    private int mem[];
    public Allocator(){}


    public Allocator(int n) {
        this.mem = new int[n];
    }
    /*
        时间复杂度 O(q * n)
        想了一下可能无法使用 二分来写
     */
    public int allocate(int size, int MID) {
        int count = 0;
        for (int i = 0; i < mem.length; i++) {
            /*
            错在 哪里
            并不能 保证 是 连续的 可用空间
            下面的代码仅仅判断了 mem[i]  和 mem[i + size - 1]  这两个位置是空闲的
            但是不能保证 i ~ i + size - 1  之间是空余的 ,因为 你没有 做判断!

             if(mem[i] == 0 && size + i - 1< mem.length && mem[size + i] == 0){
                for(int j = 0;j < size;j++){
                    mem[j + i] = MID;
                    return i;
                }
            }
             */

            // 这里考察的 coding细节还是很多的
            // 要先找到 size 个连续的空间之后,再 倒着 填值标记 ,这样 做 如果长度不够 不用去撤销
            count = mem[i] != 0 ? 0 : count + 1;
            if(count == size){
                for(int j = 0; j < count ;j++){
                    mem[i - j] = MID;
                }
                return i - count + 1;
            }
        }
        return -1;
    }


    public int free(int MID) {
        int count = 0;
        for (int i = 0; i < mem.length; i++) {
            if (mem[i] == MID) {
                count++;
                mem[i] = 0;
            }
        }

        return count;
    }

}